home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3360 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB
  1. Path: Rezonet.net!news
  2. From: ray@ultimate-tech.com (Ray Dunn)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 26 Jan 1996 00:04:16 GMT
  6. Organization: Ultimate Technographics Inc.
  7. Message-ID: <4e95q0$n8q@ns.RezoNet.NET>
  8. References: <4e61iu$p6e@villa.fc.net> <4e6p7t$1n72@cymbal.aix.calpoly.edu>
  9. NNTP-Posting-Host: 204.19.230.7
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=US-ASCII
  12. X-Newsreader: WinVN 0.99.7
  13.  
  14. In referenced article, Dan Stubbs says...
  15. >It seems like an interesting exercise to find the left bit using
  16. >a binary search since moving an appropriate mask around (for
  17. >speed) is a bit "different."  The following is for 32 bit ints,
  18. >as you can see it is simple to modify for any width int that is
  19. >a power of 2.
  20. >
  21. >/*------------------------------------------------------------------*/
  22. >int  left_most_bit (int k) {
  23. >/*   
  24. > *   returns the position of the left most bit in k assuming that
  25. > *      k != 0 and 32 bit ints. The algorithm used is essentially a
  26. > *      binary search.
  27. > */
  28. >   int posn = 0, width = 16, mask = 0xffff0000;
  29. >
  30. >   while (width > 1) {
  31. >      if (k & mask) {
  32. >         width /= 2;
  33. >         mask <<= (posn + width);
  34. >         mask >>=  posn;
  35. >      }
  36. >      else {
  37. >         mask >>= width;
  38. >         posn +=  width;
  39. >      }
  40. >   } 
  41. >   if (k & mask) return posn;
  42. >   else return posn+1;
  43. >}
  44.  
  45. Apart from the speed, and not handling the zero case, there are two 
  46. problems with this.
  47.  
  48. - The mask must be unsigned, otherwise it won't work on machines that 
  49.   shift in the sign bit on right shifts (e.g. mine!)  k should be 
  50.   unsigned too.
  51.  
  52. - You are counting bits from the msb end, so you are not producing log 
  53.   base 2 of the number.
  54. -- 
  55. Ray Dunn (opinions are my own) | Phone: (514) 938 9050
  56. Montreal                       | Phax : (514) 938 5225
  57. ray@ultimate-tech.com          | Home : (514) 630 3749
  58.  
  59.